// 文件名：stack_rpn_calculator.cpp
// 目的：用“栈”实现逆波兰表达式（RPN）求值器，支持 +, -, *, / 四则运算。
// 算法：
//   - 逐个扫描 token：
//       * 若为运算符：从栈顶弹出两个操作数（先弹出的是右操作数），计算并将结果入栈；
//       * 若为数字：转换为 double 后入栈；
//   - 完成后栈中应仅剩一个结果，否则表达式不合法。
// 健壮性：
//   - requireOperands(n)：在执行运算前检查栈内至少有 n 个操作数，否则抛出异常；
//   - 除法时检查除数为 0，避免除零；
//   - 结束时若栈元素数 != 1，则抛出“Malformed expression”。
// 复杂度：O(N)，N 为 token 数；空间 O(N)（最坏情况下全部为数字）。
// 可扩展：支持更多运算（幂、取整、函数）、一元运算符、变量与上下文环境等。

#include <cmath>
#include <iostream>
#include <stack>
#include <stdexcept>
#include <string>
#include <vector>

double evaluateRPN(const std::vector<std::string>& tokens) {
    std::stack<double> st;

    auto requireOperands = [&](std::size_t n) {
        if (st.size() < n) {
            throw std::runtime_error("Insufficient operands");
        }
    };

    for (const auto& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            requireOperands(2);
            double rhs = st.top(); st.pop();
            double lhs = st.top(); st.pop();
            if (token == "+") st.push(lhs + rhs);
            else if (token == "-") st.push(lhs - rhs);
            else if (token == "*") st.push(lhs * rhs);
            else {
                if (rhs == 0.0) throw std::runtime_error("Division by zero");
                st.push(lhs / rhs);
            }
        } else {
            st.push(std::stod(token));
        }
    }

    if (st.size() != 1) {
        throw std::runtime_error("Malformed expression");
    }
    return st.top();
}

int main() {
    std::vector<std::string> expr = {"3", "4", "2", "*", "1", "5", "-", "/", "+"};
    try {
        std::cout << "Result = " << evaluateRPN(expr) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << "Error: " << ex.what() << '\n';
    }
    return 0;
}